package leetcode.editor.cn;

import java.util.Arrays;

//[322]零钱兑换
public class CoinChange322 {
    public static void main(String[] args) {

        Solution solution = new CoinChange322().new Solution();
        //	测试用例:[1,2,5]
        //			11
        //	测试结果:0
        //	期望结果:3
        System.out.println("CoinChange322:main:" + solution.coinChange(new int[]{1, 2, 5}, 11));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        //最少的硬币数量  //	执行耗时:13 ms,击败了69.44% 的Java用户 //	内存消耗:42.9 MB,击败了99.09% 的Java用户
        public int coinChange(int[] coins, int amount) {
            if (coins == null || coins.length < 1 || amount < 1) return 0;
            //关键 定义非法的数据。-1
            int[] dp = new int[amount + 1];
            for (int i = 1; i <= amount; i++) {
                dp[i] = amount + 1;//非法的数字
                //dp[i] = Min{dp[i-...c1 ---cn]} +1
                for (int j = 0; j < coins.length; j++) {
                    int curCoin = coins[j];
                    if (i == curCoin) {
                        dp[i] = 1;
                    } else if (i > curCoin) {
                        dp[i] = Math.min(dp[i], dp[i - curCoin] + 1);
                    }
                }
            }

            return dp[amount] >= amount + 1 ? -1 : dp[amount];
        }

        //failed
        public int coinChange2(int[] coins, int amount) {
            if (coins == null || coins.length < 1 || amount < 1) return 0;
            int res = 0;
            //dp ,从大的开始。
            Arrays.sort(coins);
            int[] dp = new int[amount + 1];
            dp[0] = 0;
            for (int i = 0; i < coins.length; i++) {
                if (amount >= coins[i]) {
                    dp[coins[i]] = 1;
                }
            }
            for (int i = 1; i <= amount; i++) {
                if (dp[i] != 1) {
                    dp[i] = -1;//def 不能组合。
                } else {
                    dp[i] = 0;
                }
                //dp[i] = Min{dp[i-...c1 ---cn]} +1
                int minStep = dp[i];

                for (int j = 0; j < coins.length; j++) {
                    int curCoin = coins[j];
                    if (i >= curCoin) {
                        int preStep = dp[i - curCoin];//合法性，是不是有值
                        if (preStep == -1) continue;
                        int curStep = dp[preStep] + 1;
                        if (minStep == -1) {
                            minStep = curStep;
                        }
                        minStep = Math.min(minStep, curStep);
                    }
                }

                dp[i] = minStep;

            }

            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}